package 实现数据结构.实现队列;

/**
 * @DESC 顺序队列（数组实现）
 * 真上溢：空间满了
 * 假上溢：顺序队列为空，却无法入队的情况
 * 解决：循环队列，想象这个数组首尾相连，将tail标记重新指向开始处。
 *
 * @Author tzq
 * @Date 2019-10-19 17:10
 **/
public class ArrayQueue {

    private final Object[] items;
    private int head;
    private int tail;

    public ArrayQueue(int capacity) {
        this.items = new Object[capacity];
    }

    // 入队
    public boolean push(Object item) {
        if (head == (tail + 1) % items.length) {
            // queue is full
            return false;
        }

        items[tail] = item;
        // tail标记后移动一位
        tail = (tail + 1) % items.length;

        return true;

    }

    /**
     * 获取头元素，不出队
     *
     * @return
     */
    public Object peek() {
        if (head == tail) {
            return null;
        }
        return items[head];
    }

    /**
     * 获取头元素，出队
     *
     * @return
     */
    public Object poll() {
        if (head == tail) {
            return null;
        }
        Object item = items[head];
        // 重要，将不用的元素值设置为空
        items[head] = null;
        // head标记后面移动一位
        head = (head + 1) % items.length;
        return item;
    }

    public boolean isFull() {
        return head == (tail + 1) % items.length;
    }

    public boolean isEmpty() {
        return head == tail;
    }

    public int size() {
        if (tail >= head) {
            return tail - head;
        } else {
            //假上溢：将tail标记重新指向开始处
            // 0+6-3 = 3个元素
            return tail + items.length - head;
        }
    }

}
